package 纯01问题携带研究材料;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/6 16:52
 * @description:
 */
public class Solution2 {
    public int zoneOne(int goods, int luggage, int[] weights, int[] values) {
        // 01背包问题
        // ① dp数组以及含义：dp[i]表示从前面可以选择的物品中进行选取，当背包容量为 i 时，所能携带的最大价值
        // ② 动态转移方程：dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);。每一个物品都拥有选取/不选取两种状态
        // ③ 初始化dp数组:当只含有物品0时，背包容量需要大于value才能存放, dp[?] = value[0]
        // ④ 遍历顺序：先遍历物品，再遍历背包容量(因为这个地方修改为了一维dp，背包容量的遍历需要从大到小，防止一个物品被重复放入！)

        int[] dp = new int[luggage + 1];
        for (int i = weights[0]; i <= luggage; i++) {
            dp[i] = values[0];
        }

        print(dp);

        for (int i = 1; i < goods; i++) {
            for (int j = luggage; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
            print(dp);
        }

        return dp[luggage];
    }


    public void print(int[] dp) {
        System.out.println(Arrays.toString(dp));
    }
}
